//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#include <boost/config.hpp>
#include <iostream>
#include <iterator>
#include <vector>
#include <list>
// Use boost::queue instead of std::queue because std::queue doesn't
// model Buffer; it has to top() function. -Jeremy
#include <boost/pending/queue.hpp>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_utility.hpp>

using namespace std;
using namespace boost;
/*
  This example does a best-first-search (using dijkstra's) and
  simultaneously makes a copy of the graph (assuming the graph is
  connected).

  Example Graph: (p. 90 "Data Structures and Network Algorithms", Tarjan)

              g
            3+ +2
            / 1 \
           e+----f
           |+0 5++
           | \ / |
         10|  d  |12
           |8++\7|
           +/ | +|
           b 4|  c
            \ | +
            6+|/3
              a

  Sample Output:
a --> c d
b --> a d
c --> f
d --> c e f
e --> b g
f --> e g
g -->
Starting graph:
a(32767); c d
c(32767); f
d(32767); c e f
f(32767); e g
e(32767); b g
g(32767);
b(32767); a d
Result:
a(0); d c
d(4); f e c
c(3); f
f(9); g e
e(4); g b
g(7);
b(14); d a

*/

typedef property< vertex_color_t, default_color_type,
    property< vertex_distance_t, int > >
    VProperty;
typedef int weight_t;
typedef property< edge_weight_t, weight_t > EProperty;

typedef adjacency_list< vecS, vecS, directedS, VProperty, EProperty > Graph;

template < class Tag >
struct endl_printer : public boost::base_visitor< endl_printer< Tag > >
{
    typedef Tag event_filter;
    endl_printer(std::ostream& os) : m_os(os) {}
    template < class T, class Graph > void operator()(T, Graph&)
    {
        m_os << std::endl;
    }
    std::ostream& m_os;
};
template < class Tag > endl_printer< Tag > print_endl(std::ostream& os, Tag)
{
    return endl_printer< Tag >(os);
}

template < class PA, class Tag >
struct edge_printer : public boost::base_visitor< edge_printer< PA, Tag > >
{
    typedef Tag event_filter;

    edge_printer(PA pa, std::ostream& os) : m_pa(pa), m_os(os) {}

    template < class T, class Graph > void operator()(T x, Graph& g)
    {
        m_os << "(" << get(m_pa, source(x, g)) << "," << get(m_pa, target(x, g))
             << ") ";
    }
    PA m_pa;
    std::ostream& m_os;
};
template < class PA, class Tag >
edge_printer< PA, Tag > print_edge(PA pa, std::ostream& os, Tag)
{
    return edge_printer< PA, Tag >(pa, os);
}

template < class NewGraph, class Tag >
struct graph_copier
: public boost::base_visitor< graph_copier< NewGraph, Tag > >
{
    typedef Tag event_filter;

    graph_copier(NewGraph& graph) : new_g(graph) {}

    template < class Edge, class Graph > void operator()(Edge e, Graph& g)
    {
        add_edge(source(e, g), target(e, g), new_g);
    }

private:
    NewGraph& new_g;
};
template < class NewGraph, class Tag >
inline graph_copier< NewGraph, Tag > copy_graph(NewGraph& g, Tag)
{
    return graph_copier< NewGraph, Tag >(g);
}

template < class Graph, class Name > void print(Graph& G, Name name)
{
    typename boost::graph_traits< Graph >::vertex_iterator ui, uiend;
    for (boost::tie(ui, uiend) = vertices(G); ui != uiend; ++ui)
    {
        cout << name[*ui] << " --> ";
        typename boost::graph_traits< Graph >::adjacency_iterator vi, viend;
        for (boost::tie(vi, viend) = adjacent_vertices(*ui, G); vi != viend;
             ++vi)
            cout << name[*vi] << " ";
        cout << endl;
    }
}

int main(int, char*[])
{
    // Name and ID numbers for the vertices
    char name[] = "abcdefg";
    enum
    {
        a,
        b,
        c,
        d,
        e,
        f,
        g,
        N
    };

    Graph G(N);
    boost::property_map< Graph, vertex_index_t >::type vertex_id
        = get(vertex_index, G);

    std::vector< weight_t > distance(N, (numeric_limits< weight_t >::max)());
    typedef boost::graph_traits< Graph >::vertex_descriptor Vertex;
    std::vector< Vertex > parent(N);

    typedef std::pair< int, int > E;

    E edges[] = { E(a, c), E(a, d), E(b, a), E(b, d), E(c, f), E(d, c), E(d, e),
        E(d, f), E(e, b), E(e, g), E(f, e), E(f, g) };

    int weight[] = { 3, 4, 6, 8, 12, 7, 0, 5, 10, 3, 1, 2 };

    for (int i = 0; i < 12; ++i)
        add_edge(edges[i].first, edges[i].second, weight[i], G);

    print(G, name);

    adjacency_list< listS, vecS, directedS,
        property< vertex_color_t, default_color_type > >
        G_copy(N);

    cout << "Starting graph:" << endl;

    std::ostream_iterator< int > cout_int(std::cout, " ");
    std::ostream_iterator< char > cout_char(std::cout, " ");

    boost::queue< Vertex > Q;
    boost::breadth_first_search(G, vertex(a, G), Q,
        make_bfs_visitor(boost::make_list(
            write_property(make_iterator_property_map(name, vertex_id, name[0]),
                cout_char, on_examine_vertex()),
            write_property(make_iterator_property_map(
                               distance.begin(), vertex_id, distance[0]),
                cout_int, on_examine_vertex()),
            print_edge(make_iterator_property_map(name, vertex_id, name[0]),
                std::cout, on_examine_edge()),
            print_endl(std::cout, on_finish_vertex()))),
        get(vertex_color, G));

    std::cout << "about to call dijkstra's" << std::endl;

    parent[vertex(a, G)] = vertex(a, G);
    boost::dijkstra_shortest_paths(G, vertex(a, G),
        distance_map(make_iterator_property_map(
                         distance.begin(), vertex_id, distance[0]))
            .predecessor_map(make_iterator_property_map(
                parent.begin(), vertex_id, parent[0]))
            .visitor(
                make_dijkstra_visitor(copy_graph(G_copy, on_examine_edge()))));

    cout << endl;
    cout << "Result:" << endl;
    boost::breadth_first_search(G, vertex(a, G),
        visitor(make_bfs_visitor(boost::make_list(
            write_property(make_iterator_property_map(name, vertex_id, name[0]),
                cout_char, on_examine_vertex()),
            write_property(make_iterator_property_map(
                               distance.begin(), vertex_id, distance[0]),
                cout_int, on_examine_vertex()),
            print_edge(make_iterator_property_map(name, vertex_id, name[0]),
                std::cout, on_examine_edge()),
            print_endl(std::cout, on_finish_vertex())))));

    return 0;
}
